package com.example.question.tree.tree3;

import java.util.LinkedList;
import java.util.Queue;

public class Code05_116 {
    private static int index; // 全局索引变量

    public static void main(String[] args) {
        Node treeNode = createTree(new Integer[]{1, 2, 4, null, null, 5, null, null, 3, 6, null, null, 7, null, null});
        Code05_116 code = new Code05_116();
        code.connect(treeNode);


    }

    // BFS  宽度优先搜索
    public Node connect(Node root) {
        if (root == null) return null;
        bfs(root);
        return root;
    }

    public void bfs(Node node) {
        Queue<Node> queue = new LinkedList<>();
        queue.offer(node);
        while (!queue.isEmpty()) {
            int size = queue.size();
            Node cur = queue.peek();
            for (int i = 0; i < size; i++) {
                Node poll = queue.poll();
                if (i >= 1) {
                    cur.next = poll;
                    cur = cur.next;

                }
                if (poll.left != null) {
                    queue.offer(poll.left);
                }
                if (poll.right != null) {
                    queue.offer(poll.right);
                }
            }
        }
    }

    static class Node {
        Node left;
        Node right;
        Node next;
        int val;

        public Node(int val) {
            this.val = val;
        }

        @Override
        public String toString() {
            return "Node{" +
                    "val=" + val +
                    ", left=" + left +
                    ", right=" + right +
                    ", next=" + next +
                    '}';
        }
    }

    public static Node createTree(Integer[] nums) {
        index = 0; // 初始化索引变量
        return createTreeHelper(nums);
    }

    public static Node createTreeHelper(Integer[] nums) {
        if (index >= nums.length || nums[index] == null) {
            index++; // 跳过 null 节点
            return null;
        }
        Node treeNode = new Node(nums[index]);
        index++; // 增加索引
        treeNode.left = createTreeHelper(nums);
        treeNode.right = createTreeHelper(nums);
        return treeNode;
    }

}
